[BAEKJOON] 1103. 게임

Posted on January 18, 2021

문제 :

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

입력 :

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력 :

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

풀이 :

문제를 초반에 너무 어렵게 접근한 탓에 로직을 다듬느라 시간이 많이 걸린 문제였다.

문제는 생각보단 단순하다. 무난하게 경로를 탐색하면 되는 문제인데 조금 다른 점이 있다면 동전이 무한하게 움직일 경우를 선별해낼 수 있어야 한다.

초반부터 무한히 움직일 경우는 밟은 칸을 다시 밟게 되는 경우라고 정리할 수 있었지만 그 점을 어떻게 구현할지 생각하는데 좀 헷갈리는 점이 몇 군데 있었다.

결론적으로 말하자면 내가 구현한 방식은 visit 배열과 dp 배열을 모두 사용한 dfs 방식으로 문제를 해결했다.

dfs 방식으로 깊이 탐색을 통해 경로를 찾아본다.
visit 배열을 말 그대로 해당 칸을 탐색하는 과정에서 한 번이라도 밟은 적이 있는지 체크하는 용도이다.
dp 배열은 크게 두가지 기능을 한다. 먼저 기본적으로 해당 칸을 탐색한 적이 있다면 해당 칸의 최대 깊이(최대 이동 횟수)를 저장하는 용도로 쓰인다.
dp 배열의 두번째 기능으로는 무한 경로인지 아닌지 체크하는 용도이다. dp 배열은 초반 0으로 모두 초기화 되어있는데 만약 visit 배열에서는 true로 방문한 적이 있는 칸인데 dp 배열이 그대로 0이란 말은 현재 dfs의 한 경로에서 중복적으로 방문했다는 말이기 때문에 무한 경로로 판단하게 되는 것이다.

코드 :

코드 보기/접기

#include <iostream>
#include <algorithm>

using namespace std;
char map[50][50];
bool visit[50][50];
int n, m, di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0}, dp[50][50];

int dfs(int x, int y) {
    if (visit[x][y]) {
        if (dp[x][y]) return dp[x][y];
        return -1;
    }

    int move = map[x][y] - '0', result, curcnt = 0;
    visit[x][y] = true;
    for (int k = 0; k < 4; k++) {
        int cmpx = x + move * di[k], cmpy = y + move * dj[k];
        if (0 <= cmpx && cmpx < n && 0 <= cmpy && cmpy < m) {
            if (map[cmpx][cmpy] == 'H') continue;
            result = dfs(cmpx, cmpy);
            if (result == -1) return -1;
            curcnt = max(curcnt, result);
        }
    }
    return dp[x][y] = curcnt + 1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> map[i][j];
    cout << dfs(0, 0) << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++